package com.interview.javabasic.Search;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import java.util.ArrayList;
import java.util.List;

public class BinarySearch{
    //二分查找的前提是数组时有序的
    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1000,1000,1234};
        System.out.println("resultIndex： " +binarySearch(arr,0,arr.length-1,80) );

    }
    public static int binarySearch(int arr[],int left,int right,int val){
       if (left > right){
           return -1;
       }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (val > midVal){
           return binarySearch(arr,mid+1,right,val);
        }else if (val < midVal){
            return binarySearch(arr,left,mid-1,val);
        }else {
            return mid;
        }

    }

    //找出所有存在这个数的下标
    public static ArrayList<Integer> binarySearch2(int arr[], int left, int right, int val){
        if (left > right){
            return new ArrayList<>();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (val > midVal){
            return binarySearch2(arr,mid+1,right,val);
        }else if (val < midVal){
            return binarySearch2(arr,left,mid-1,val);
        }else {
            ArrayList<Integer> resIndexlist = new ArrayList<>();
            int tmp = mid - 1;
            while (true){
                if (tmp < 0 || arr[tmp] !=val){
                    break;
                }
                resIndexlist.add(tmp);
                tmp -=1;
            }
            resIndexlist.add(mid);
            tmp = mid+1;
            while (true){
                if (tmp <arr.length - 1 || arr[tmp] !=val){
                    break;
                }
                resIndexlist.add(tmp);
                tmp +=1;
            }

            return resIndexlist;
        }

    }
}
